package class7;

import common.Node;

/**
 * 题目1：
 * 给定两个可能有环也可能无环的单链表，头肩点head1和head2,
 * 请事先一个函数，如果两个链表相交，请返回相交的第一个节点，如果不相交，返回null
 * 要求
 * 如果两个链表的长度之和为N，时间复杂度请达到 O(N)，额外空间复杂度请达到 O(1)
 * <p>
 * 环形链表:https://leetcode.cn/problems/linked-list-cycle/description/
 * 环形链表2:https://leetcode.cn/problems/c32eOV/description/
 */
public class Code01_DoubleLinked {
    public static void main(String[] args) {

    }

    /**
     * 如果是环形链表，返回进入环的首节点
     * 快慢指针
     */
    public static Node getLoopNode(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        // n1慢 n2快
        Node n1 = head.next; // n1 -> slow
        Node n2 = head.next.next; // n2 -> fast
        while (n2 != n1) { // 如果 n2 与 n1 不相遇
            if (n2.next == null || n2.next.next == null) {
                return null;
            }
            n2 = n2.next.next;
            n1 = n1.next;
        }
        // 快慢指针相遇
        n2 = head; // 快指针从head开始
        while (n2 != n1) {
            n1 = n1.next;
            n2 = n2.next;
        }

        return n1;
    }

    // 判断一个链表是否有环，
    public static boolean isLoopNode(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return false;
        }
        // n1慢 n2快
        Node n1 = head.next; // n1 -> slow
        Node n2 = head.next.next; // n2 -> fast
        while (n2 != n1) { // 如果 n2 与 n1 不相遇
            if (n2.next == null || n2.next.next == null) {
                return false;
            }
            n2 = n2.next.next;
            n1 = n1.next;
        }
        return true;
    }
}
